package com.study;

import com.study.common.TreeNode;

import java.util.Stack;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-14 13:51
 * @version: 1.0
 * @description: 二叉树遍历
 **/
public class BinaryTree {
    public static void main(String[] args) {
        TreeNode node7 = new TreeNode(7,null,null);
        TreeNode node6 = new TreeNode(6,null,null);
        TreeNode node5 = new TreeNode(5,node6,node7);
        TreeNode node4 = new TreeNode(4,null,null);
        TreeNode node3 = new TreeNode(3,null,null);
        TreeNode node2 = new TreeNode(2,node4,node5);
        TreeNode node1 = new TreeNode(1,node2,node3);
        preorder(node1);
        System.out.println("====================");
        morrisPre1(node1);
//        morrisPost(node1);
    }

    // 递归实现：前序遍历是当你第一次成为栈顶元素时打印
    private static void preorder(TreeNode root) {
        if (root == null) return;
        System.out.println(root.val);
        preorder(root.left);
        preorder(root.right);
    }

    /*
     morris 遍历中的一些概念：
     1、找前驱节点：就是当前节点的 左子树的找最右边的节点
     2、前驱节点的右指针指向的是它自己，就意味着要删除该指向记录(释放指针)
     */
    private static void morrisPre(TreeNode root){
        if (root == null){
            return;
        }
        TreeNode curr = root;
        while (curr != null){
            TreeNode mostRight = curr.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != curr){
                    mostRight =  mostRight.right;
                }

                if (mostRight.right == null){// 建立前驱节点
                    mostRight.right = curr;
                    System.out.println(curr.val);
                    curr = curr.left;
                    continue;
                }else {
                    mostRight.right = null;
                }
            }else {
                System.out.println(curr.val);
            }
            curr = curr.right;
        }
    }

    private static void morrisMid(TreeNode root){
        if (root == null){
            return;
        }
        TreeNode curr = root;
        while (curr != null){
            TreeNode mostRight = curr.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != curr){
                    mostRight =  mostRight.right;
                }

                if (mostRight.right == null){// 建立前驱节点
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                }else {
                    mostRight.right = null;
                }
            }
            System.out.println(curr.val);
            curr = curr.right;
        }
    }


    private static void morrisPost(TreeNode root){
        if (root == null){
            return;
        }
        TreeNode curr = root;
        while (curr != null){
            TreeNode mostRight = curr.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != curr){
                    mostRight =  mostRight.right;
                }

                if (mostRight.right == null){// 建立前驱节点
                    mostRight.right = curr;
                    curr = curr.left;
                    continue;
                }else {
                    mostRight.right = null;
                    printNode(curr.left);
                }
            }
            curr = curr.right;
        }
        printNode(root);
    }

    private static void printNode(TreeNode head) {
        TreeNode tail = reverse(head);
        while (tail != null){
            System.out.println(tail.val);
            tail = tail.right;
        }
        reverse(head);
    }

    private static TreeNode reverse(TreeNode head) {
        TreeNode prev = null, curr = head,next;
        while (curr != null){
            next = curr.right;
            curr.right = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }


    // 递归实现：前序遍历是当你第一次成为栈顶元素时打印
    private static void preorderIterate(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        while (!stack.isEmpty()){
            TreeNode pop = stack.pop();
            System.out.println(pop.val);
            if (pop.right != null){
                stack.add(pop.right);
            }
            if (pop.left != null){
                stack.add(pop.left);
            }
        }
    }

    private static void midOrderIterate(TreeNode root) {
        if (root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null){
            if (root != null){
                stack.push(root);
                root = root.left;
            }else {
                root = stack.pop();
                System.out.println(root.val);
                root = root.right;
            }
        }
    }


    /*
    morris 遍历中的一些概念：
    1、找前驱节点：就是当前节点的 左子树的找最右边的节点
    2、前驱节点的右指针指向的是它自己，就意味着要删除该指向记录(释放指针)
    */
    private static void morrisPre1(TreeNode root){
        if (root == null) return;

        TreeNode curr = root,mostRight;
        while (curr != null){
            mostRight = curr.left;
            if (mostRight != null){
                while (mostRight.right != null && mostRight.right != curr){
                    mostRight = mostRight.right;
                }
                if (mostRight.right == null){ // 建立前驱节点
                    mostRight.right = curr;
//                    System.out.println(curr.val);
                    curr = curr.left;
                    continue;
                }else { // 删除前驱节点
                    mostRight.right = null;
                }
            }else {
//                System.out.println(curr.val);
            }
            System.out.println(curr.val);
            curr = curr.right;
        }




    }

}
